/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <unistd.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name (id1+id2)*/
    "Abhishek",
    /* First member's full name */
    "Abhishek Anand",
    /* First member's email address */
    "abhishekanand149@gmail.com",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};


#define BLOCKFAIL (void*) -1
#define EMPTY_LIST (void*) -1
#define NUM_FREE_LISTS 30



/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)


#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))



typedef struct FreeListNode {
    struct FreeListNode* next;
    struct FreeListNode* prev;
    size_t size;
    void* position;
} FreeListNode;

typedef void* heap_index;
typedef size_t size_class;

heap_index heap_start;








/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    heap_start = mem_sbrk(NUM_FREE_LISTS * sizeof(heap_index));
    heap_index current_index = heap_start;

    // Initialize all list pointers to EMPTY_LIST
    for (int i = 0; i < NUM_FREE_LISTS; i++) {
        *current_index = EMPTY_LIST;
        current_index++;
    }
    return 0;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size)
{
    int newsize = ALIGN(size + SIZE_T_SIZE);
    void *p = find_free_block(newsize);
    if (p == BLOCKFAIL)
        p = alloc_new_block(newsize);

    mark_as_allocated(p);
    return p // Which could be null
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
	void* new_block_start = coalesce(ptr);
    push_free_list(new_block_start);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

static void* find_free_block(int requestSize) {
    size_t class = get_size_class(requestSize);
    heap_index free_list = get_free_list(class);
    if (free_list == EMPTY_LIST)
        return BLOCKFAIL;

    // Else, traverse the list
    while (current_block != EMPTY_LIST) {
        

        current_block = next(current_block)
    }
}


static heap_index free_list_next(heap_index block) {
    heap_index 


}


static FreeListNode* get_free_list(size_class class) {
    // 8 -> heap_start
    // 16 -> heap_start + 1
    // n -> heap_start + log_2(n) - 3
    return heap_start + log2(class) - 3;
} 

static size_class get_size_class(size_t size) {
    // Find the lowest power of two
    int class = 8;
    do {
        class << 1;
    } while (class < size);

    return class >> 1;
}

int log2(n) {
    return (int) floor(log(n) / log(2));
}












